package com.example.question.list.list2;

import com.example.question.list.list1.List;
import com.example.question.list.list1.ListNode;

/**
 * @Date 2023-07-08
 * @Author Jonathan
 * @link {<a href="https://leetcode.cn/problems/add-two-numbers-ii/">...</a>}
 */
public class Code06_445 {
    public static void main(String[] args) {
        Code06_445 code = new Code06_445();
        ListNode l1 = List.createList(new int[]{7, 2, 4, 3});
        ListNode l2 = List.createList(new int[]{5, 6, 4});
        System.out.println(code.addTwoNumbers(l1, l2));
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1.val == 0) {
            return l2;
        }
        if (l2.val == 0) {
            return l1;
        }
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode retHead = new ListNode(-1);
        ListNode retCur = retHead;
        // 进位
        int carry = 0;
        while (cur1 != null && cur2 != null) {
            int val = (cur1.val + cur2.val + carry) % 10;
            carry = (cur1.val + cur2.val + carry) / 10;
            retCur.next = new ListNode(val);
            retCur = retCur.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        while (cur1 != null) {
            int val = (cur1.val + carry) % 10;
            carry = (cur1.val + carry) / 10;
            retCur.next = new ListNode(val);
            retCur = retCur.next;
            cur1 = cur1.next;
        }

        while (cur2 != null) {
            int val = (cur2.val + carry) % 10;
            carry = (cur2.val + carry) / 10;
            retCur.next = new ListNode(val);
            retCur = retCur.next;
            cur2 = cur2.next;
        }
        // 最后一次还占用进位的话  还要新增一个节点
        if (carry > 0) {
            retCur.next = new ListNode(carry);
        }
        return reverse(retHead.next);
    }


    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode ret = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return ret;
    }
}
